package com.platform.modules.alg.alglib.p3690;

public class P3690 {
    private int MAXN = 300005;
    int n, m;
    int a[] = new int[MAXN];

    int top;
    int c[][] = new int[MAXN][2];
    int fa[] = new int[MAXN];
    int v[] = new int[MAXN];
    int st[] = new int[MAXN];
    int rev[] = new int[MAXN];


    public String output = "";

    // 更新当前节点的值（路径上点值 XOR ）
    void update(int x) {
        v[x] = v[c[x][0]] ^ v[c[x][1]] ^ a[x];
    }

    // 下传懒惰标记
    void pushdown(int x) {
        if (rev[x] == 1) {
            rev[c[x][0]] ^= 1;
            rev[c[x][1]] ^= 1;
            rev[x] ^= 1;
            int temp = c[x][0];
            c[x][0] = c[x][1];
            c[x][1] = temp;
        }
    }

    // 判断是否是所在 Splay 的根节点
    boolean isroot(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }

    // 旋转，将x变成y的父节点
    void rotate(int x) {
        int y = fa[x], z = fa[y], k;
        if (c[y][0] == x) {
            k = 1;
        } else {
            k = 0;
        }
        // 如果 y 不是根节点，那么将 z 的儿子 y 变成 x
        if (!isroot(y)) c[z][c[z][1] == y ? 1 : 0] = x;
        fa[x] = z;
        fa[y] = x;
        fa[c[x][k]] = y;
        c[y][k == 0 ? 1 : 0] = c[x][k];
        c[x][k] = y;
        update(y);
        update(x);
    }

    void splay(int x) {
        st[top = 1] = x;
        for (int i = x; !isroot(i); i = fa[i]) st[++top] = fa[i];//一定要从上往下
        while (top > 0) pushdown(st[top--]);
        while (!isroot(x)) {//将x旋到根
            int y = fa[x], z = fa[y];
            if (!isroot(y)) {
                if (c[y][0] == x ^ c[z][0] == y) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
    }

    // 连接一条 x 到根的实链
    void access(int x) {
        for (int y = 0; x > 0; x = fa[y = x]) {
            splay(x);
            c[x][1] = y;
            update(x);
        }
    }

    // 换根，将x变成原树的根
    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }

    // 找 x 的根节点
    int findroot(int x) {
        access(x);
        splay(x);
        while (c[x][0] > 0) x = c[x][0];
        return x;
    }

    // 拉出一条 x 到 y 的路径为一个 Splay
    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }

    // 删除一条 x 到 y 的边
    void cut(int x, int y) {
        split(x, y);
        if (c[y][0] != x || c[x][1] > 0) return; // 坑点，此时 x 是 y 的左儿子，且 x 没有右儿子，如果有说明x--y中间有节点
        c[y][0] = fa[c[y][0]] = 0;
        update(y);
    }

    // 连一条 x 到 y 的虚边
    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        m = Integer.parseInt(word[1]);

        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(line[i]);
            v[i] = a[i];
        }
        int count = 1;
        while (m-- > 0) {
            int opt, x, y;
            String[] query = line[n + count++].split(" ");
            opt = Integer.parseInt(query[0]);
            x = Integer.parseInt(query[1]);
            y = Integer.parseInt(query[2]);

            if (opt == 0) {
                split(x, y);
                output += v[y] + "\n";
            } else if (opt == 1) {
                if (findroot(x) != findroot(y)) // 不连通
                    link(x, y);
            } else if (opt == 2) {
                if (findroot(x) == findroot(y)) // 连通
                    cut(x, y);
            } else if (opt == 3) {
                splay(x);
                a[x] = y;
            }
        }
        return output;
    }
}
